NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/8544

Text File | 1996-08-05 | 3.8 KB | 141 lines

Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
Path: cwi.nl!dik
From: [e-mail] (Dik T. Winter)
Subject: Re: Tough FACTORIAL math problem...
Message-ID: <[e-mail]>
Sender: [e-mail] (The Daily Dross)
Nntp-Posting-Host: chrysant.cwi.nl
Organization: CWI, Amsterdam
References: <4fr8be$[e-mail]> <4g0giv$[e-mail]>
Date: Fri, 16 Feb 1996 02:21:51 GMT

In article <4g0giv$[e-mail]> [e-mail] (Kevin Cline) writes:

[Note: at the end there is a complete explanation of the problem and the
solution.  At first here follows a flamelet.]

 > Everyone had the right idea, which is to keep only the last digit
 > and compute the change when multiplying by the next number
 > in the factorial, but couldn't figure out what to do
 > about the numbers that end in 5, since that introduces a new zero
 > in the series.  The answer is simple; when multiplying by five,
 > take half of the previous digit +-5 to make an even number.

But you did it only halfway, see below.
 >
 > This works because 5 always follows 4, 4 x 5 = 20 (2),
 > and 2 is half of 4.

It is well known that in all cases the number of 5's is far less than
the number of 2's in the factorial; k.5^n where k does not contain a
factor 5, follows k.2^n.

 >     int last_non_zero_digit_of_factorial(n) {
 >       digit = 1;
 >       for (int i = 2; i < n ; ++i) {
 >     while (i % 10 == 0) i /= 10;
 >     digit = table[digit-1][i-1];
 >       }
 >       return digit;
 >     }
I get (with main(){int i; for(i=1;i<=25;i++)printf("%d %d\n",i,ldof(i));}):

1 1
2 1
3 2
4 0
Memory fault(coredump)

After interchanging "digit-1" and "i-1" I get
1 1
2 1
3 2
4 6
5 4
6 8
7 8
8 6
9 8
10 2
after which it loops forever.

Changing the loop so that it uses a new variable rather than the loop
variable I get:
1 1
2 1
3 2
4 6
5 4
6 8
7 8
8 6
9 8
10 2
11 2
12 268566528
Memory fault(coredump)

Changing the terminating loop condition to <= n gives me:
1 1
2 2
3 6
4 4
5 8
6 8
7 6
8 8
9 2
10 2
11 268566528
Memory fault(coredump)

Changing the faulty fifth line of the intialization of table to
{0, 6, 0, 2, 0, 8, 0, 4, 0 }, gives me:
1 1
2 2
3 6
4 4
5 2
6 2
7 4
8 2
9 8
10 8
11 268697600
Memory fault(coredump)

Finally changing i1-1 in the indexing to i1%10-1 the program kept running,
but it gives 6 as last digit for 15!.

Did you try your function?

[End of flamelet.]

What you and most other posters (except the one I saw in maple, and my
own of course) forget is that if a number contains factors of 5 you have
to be aware of all factors 5 plus the remainder divided by all those
factors. 14! ends in 2, lets see what happens if you multiply by 15.
First take the factor of 5; this will take 2 to 10 and a last digit
of 1; but (as you already saw) that is not valid so the last digit will
become 6.  Now you still have the remaining factor 3 which will take
6 to 8.  And, indeed, the last non-zero digit of 15! is 8.

Jochen Schoof's solution inherently used a similar table, but he ignored
the possibility of multiple factors 5.  Which (in his case) did result
for some factorials in odd last non-zero digits, and that can not happen
(except for 0! and 1!).

Using only the last k digits of the factorial (excluding trailing zeros)
and the last l digits of the multiplier will ultimately lead to a
period.  (The proof is fairly simple.)  But the last non-zero digit of
the factorial does not show a period; the increasing number of factors 5
that can occur in a single number prevent this.  So, all such methods
will fail at some stage.  Taking care of all individual factors 5 solves
this.

But apparently this is a tough question indeed.  Even an old-timer like
Jos Horsmeier fell into at least one of the traps.
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/